package com.gyg.程序员面试金典;

import java.util.Stack;

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

/**
 * 面试题 03.04. 化栈为队
 * 题目：实现一个MyQueue类，该类用两个栈来实现一个队列。
 * 解题思路：
 * 栈的出栈顺序刚好和队列的出队顺序相反，
 * 所以需要使用两个栈，从第一个栈中出来之后压入另一个栈中，这样从第二个栈中出栈的元素顺序就和队列出队列顺序一样了
 * 使用一个栈来专门写入元素，另一个栈专门读出元素，（将第一个出栈的元素压入该栈中，）
 * 每当读出栈的元素为空时，就将写入栈的元素压入，
 * （相当于是一个写入栈和一个读出栈，共同构成了一个队列，）
 * （将读出栈和写入栈从左向右看，看做一个U。就好像是一个弯曲的队列）
 */
public class T03_04 {

    //    （1）定义一个栈来写入元素
    Stack<Integer> writeStack = new Stack<Integer>();
    //    （2）定义一个栈来读出元素
    Stack<Integer> readStack = new Stack<Integer>();

    public static void main(String[] args) {
        T03_04 t03_04 = new T03_04();
        t03_04.peek();
    }

    /**
     * Initialize your data structure here.
     */
    public T03_04() {

    }

    /**
     * 入队列
     * Push element x to the back of queue.
     */
    public void push(int x) {
//        （3）从读出栈中取出栈顶元素，作为出队列的对头元素
        writeStack.push(x);
    }

    /**
     * 删除队头元素
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
//        （4）判断读出栈是否为空，如果是空的，就将写入栈的元素全都压入读出栈中
        if (readStack.isEmpty()) {
//            （5）利用循环来将写入栈的元素全都压入读出栈中
            while (!writeStack.isEmpty()) {
                readStack.push(writeStack.pop());
            }
        }
//        （6）返回并删除读出栈的栈顶元素
        return readStack.pop();
    }

    /**
     * 读取队头元素
     * Get the front element.
     */
    public int peek() {
//        和第四步一样，判断读出栈是否为空，
        if (readStack.isEmpty()) {
            while (!writeStack.isEmpty()) {
                readStack.push(writeStack.pop());
            }
        }
//（7）返回读出栈的栈顶元素，但是不删除
        return readStack.peek();
    }

    /**
     * 判断队列是否为null
     * Returns whether the queue is empty.
     */
    public boolean empty() {
//        （8）如果读出栈和写入栈都为空，才能代表队列为空
        return readStack.isEmpty() && writeStack.isEmpty();
    }
}
